#!/usr/bin/python
# -*- coding: UTF-8 -*-

"""
Miguel Silva, 6311
Estrutura de Dados e Algoritmos
Engenharia Informática 
2012/2013
"""

import sys
sys.setrecursionlimit(999999)

class QuicksortClass(object):
	"""
	Classe utilizada para representação do algoritmo de 
	ordenação Quicksort que se baseia no principio de
	divisão e conquista.
	"""
	def __init__(self):
		"""
		Constructor da classe QuicksortClass.
		"""
		super(QuicksortClass, self).__init__()


	def quicksort(self, list, p, r):
		"""
		Função que principal do algoritmo que faz a chamada à 
		função que efectua o particionamento, em que é devolvido
		o indice mediano da lista. De seguida, é feita a chamada
		recursiva da função quicksort para as duas sublistas.
		
		Argumentos:
		list -- lista
		p -- primeira posição
		r -- tamanho da lista
		"""
		if p < r:
			q = self.partition(list, p, r)
			self.quicksort(list, p, q-1)
			self.quicksort(list, q+1, r)


	def partition(self, list, p, r):
		"""
		Função que efectua o processo de particionamento e,
		reorganiza a lista de acordo com valores passados por parâmetro.
		
		Argumentos:
		list -- lista
		p -- primeira posição
		r -- tamanho da lista

		Return:
		O valor da operação index+1
		"""
		x = list[r]
		index = p - 1
		for j in xrange(p, r):
			if list[j] <= x:
				index = index + 1
				list[index], list[j] = list[j], list[index]

		list[index+1], list[r] = list[r], list[index+1]
		return index+1